import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2025-01-23
 * Time: 13:43
 */
class Pair<K,V>{
    private K key;
    private V value;
    public Pair(K key , V value){
        this.key = key;
        this.value = value;
    }
    public K getKey(){
        return key;
    }
    public V getValue(){
        return value;
    }
}
class Solution3 {
    public List<String> topKFrequent(String[] words, int k) {
        //我的两个问题——1：怎么把map中的元素按照重写的比较规则放入到堆里面
        //2：因为map中是键值对结构，但是堆只能放一个类型，怎么放是一个问题

        //第一步：把所有字符串放入map中，map结构去重
        Map<String,Integer> map = new HashMap<>();
        for(String str : words){
            map.put(str,map.getOrDefault(str,0)+1);
        }

        //第二步：new 一个堆  重写比较规则
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b)->{
                    //如果出现频次相同，按字母顺序返回，创建大根堆，可以理解成首字母更小的往堆的更深处放
                    if(a.getValue().equals(b.getValue())){
                        return (b.getKey().compareTo(a.getKey()));//对啊，compareTo方法怎么放啊
                    }
                    //依据频次创建小根堆
                    return (a.getValue()-b.getValue());
                }
        );

        //第三步：遍历map，把元素放到堆里面
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            heap.offer(new Pair<>(entry.getKey(),entry.getValue()));
            if(heap.size() > k){
                heap.poll();
            }
        }


        //第四步：让堆不断弹出元素，注意逆序(不逆序就倒着填入数组)，这里采用集合的方式
        List<String> list = new ArrayList<>();
        for(int i = 0 ; i < k ; i++){
            String s = heap.peek().getKey();
            list.add(s);
            heap.poll();
        }
        Collections.reverse(list);
        return list;
    }
}





public class Test3 {
}
